//广度优先
//用队列实现
//两个辅助数组依旧没有区别
//广度优先返回最短路径
import edu.princeton.cs.algs4.*;
public class Path_BFS {
    boolean marked[];
    int edgeTo[];   
    int s;           //起点
    //在图g中以s为起点
    public Path_BFS(Graph g,int s)
    {
        marked=new boolean[g.V()];
        edgeTo=new int[g.E()];
        this.s=s;
        Bfs(g);
    }

    public void Bfs(Graph g)
    {
        Queue<Integer> points=new Queue<Integer>();
        points.enqueue(s);
        while (!points.isEmpty()) {
           int v=points.dequeue();
           marked[v]=true;
           for(int point:g.adj(v))
           {
              if(!marked[point])
              {
              points.enqueue(point);
              edgeTo[point]=v;
              }
           }
        }
        
    }
     
    //有没有从s到v的路径
    public boolean HasPathTo(int v)
    {
        return marked[v];
    }

    //从v到s的路径
    Iterable<Integer> PathTo(int v)
    {
        if(!HasPathTo(v))
        {
            return null;
        }
        Stack<Integer> path=new Stack<Integer>();
        for(int i=v;i!=s;i=edgeTo[i])
        {
            path.push(i);
        }
        path.push(s);
        return path;
    }
}
